package datastructure.tree;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/25 9:41 下午
 */
public class BinaryHeap<T extends Comparable<? super T>> {
    private T[]array;
    private int currentSize;

    public BinaryHeap() {
        this(10);
    }
    public BinaryHeap(int cap){
        this.array= (T[]) new Comparable[cap+1];
    }

    public BinaryHeap(T[]array){
        this.array= (T[]) new Comparable[array.length];

    }

    /**
     * 插入
     * @param item
     */
    public void insert(T item){
        if (currentSize==array.length-1){
            enlargeSize(array.length*2+1);
        }
        int hole=++currentSize;
        array[0]=item;
        percolateUp(hole,item);
    }

    public T delMin(){
        if (isEmpty()){
            return null;
        }
        T min=findMin();
        if (min!=null){
            array[1]=array[currentSize--];
            percolateDown(1);
        }
        return min;
    }

    private void percolateDown(int hole) {
        T temp=array[hole];
        int child;
        for (;hole*2<=currentSize;hole=child){
            child=leftChild(hole);
            if (child!=currentSize && array[child+1].compareTo(array[child])<0){
                child++;
            }
            if (array[child].compareTo(temp)<0){
                array[hole]=array[child];
            }else {
                break;
            }
        }
        array[hole]=temp;
    }

    private int leftChild(int hole) {
        return hole*2;
    }

    private T findMin() {
        if (isEmpty()){
            return null;
        }
        return array[1];
    }

    public boolean isEmpty() {
        return currentSize==0;
    }

    private void percolateUp(int hole, T item) {
        for (;item.compareTo(array[hole/2])<0;hole/=2){
            array[hole]=array[hole/2];
        }
        array[hole]=item;
    }

    private void enlargeSize(int newSize) {
        T[]old=array;
        array= (T[]) new Comparable[newSize];
        for (int i = 0; i < old.length; i++) {
            array[i]=old[i];
        }
    }

    public static void main(String[] args) {
        BinaryHeap<Integer> heap = new BinaryHeap<>();
        heap.insert(13);
        heap.insert(14);
        heap.insert(16);
        heap.insert(19);
        heap.insert(21);
        heap.insert(19);
        heap.insert(68);
        heap.insert(65);
        heap.insert(26);
        heap.insert(32);
        heap.insert(31);
        while (!heap.isEmpty()){
            System.out.println(heap.delMin());
        }
    }
}

